package com.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * <p>
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：[3,2,3]
 * 输出：3
 * 示例 2：
 * <p>
 * 输入：[2,2,1,1,1,2,2]
 * 输出：2
 *  
 * <p>
 * 进阶：
 * <p>
 * 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xm77tm/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class 多数元素 {

	/**
	 * 方法一：先排序
	 * 题中说了给定的数组总是存在多数元素。，也就是说肯定有一个元素的个数大于数组长度的一半。我们只需要把这个数组排序，那么数组中间的值肯定是存在最多的元素。
	 */
	public static int majorityElement1(int[] nums) {
		Arrays.sort(nums);
		return nums[nums.length / 2];
	}

	/**
	 * 方法二：使用 Map 解决
	 */
	public static int majorityElement2(int[] nums) {
		Map<Integer, Integer> countMap = new HashMap<>(16);
		for (int num : nums) {
			// getOrDefault：值存在，返回对应的值，值不存在，返回指定的值
			int count = countMap.getOrDefault(num, 0) + 1;
			// 如果某个数字出现的个数已经超过数组的一半，自己返回
			if (count > nums.length / 2) {
				return num;
			}
			countMap.put(num, count);
		}
		return -1;
	}

	/**
	 * 方法三：位运算解决
	 * to see
	 */
	public static int majorityElement3(int[] nums) {
		int major = 0;
		int length = nums.length;
		//在java中int类型是32位，我们遍历每一位
		for (int i = 0, mask = 1; i < 32; i++, mask <<= 1) {
			//bitCounts表示所有数字在当前位置1的个数。比如当i=0
			//的时候，我们可以认为他表示的是所有数字在二进制位
			//中最右边1的总数。
			int bitCounts = 0;
			for (int j = 0; j < length; j++) {
				//判断数字nums[j]的第i（i从0开始）个位置是否为1，
				//如果是1，bitCounts就加1
				if ((nums[j] & mask) == mask) {
					bitCounts++;
				}
				//如果bitCounts大于数组的一半，那么这个众数在
				//这个位置肯定是1，然后通过 major |= mask运算
				//把这个位置变为1，后面不需要再判断了，直接终止
				//内层循环
				if (bitCounts > length / 2) {
					major |= mask;
					break;
				}
			}
		}
		return major;
	}

	/**
	 * 方法四：摩尔投票法
	 * 假设数组中每个不同的数字就代表一个国家，而数字的个数就代表这个国家的人数，他们在一起混战，就是每两个两个同归于尽。我们就可以知道那个人数大于数组长度一半的肯定会获胜。
	 * <p>
	 * 就算退一万步来说，其他的所有人都来攻击这个人数最多的国家，他们每两个两个同归于尽，最终剩下的也是那个众数。
	 */
	public static int majorityElement4(int[] nums) {
		// 默认第一个是多数国
		int major = nums[0];
		// 默认人数为 1
		int count = 1;
		for (int i = 1; i < nums.length; i++) {
			if (count == 0) {
				// 前边的消灭没了,再假设第二个为多数国
				count = 1;
				major = nums[i];
			} else if (major == nums[i]) {
				// 自己人，人数+1
				count++;
			} else {
				// 不是自己人，同归于尽，人数-1
				count--;
			}
		}
		return major;
	}

	public static void main(String[] args) {
		int[] array = {2, 2, 1, 1, 1, 2, 2, 1, 1};
		System.out.println(majorityElement4(array));
		System.out.println(5 & 1);
		int a = 3;
		System.out.println(a <<= 1);
	}
}
